home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / bit / RCS / bitInt.h,v < prev   
Text File  |  1988-06-19  |  5KB  |  216 lines
  1. head     1.1;
  2. access   ;
  3. symbols  ;
  4. locks    ; strict;
  5. comment  @ * @;
  6.  
  7.  
  8. 1.1
  9. date     88.06.19.14.34.53;  author ouster;  state Exp;
  10. branches ;
  11. next     ;
  12.  
  13.  
  14. desc
  15. @@
  16.  
  17.  
  18.  
  19. 1.1
  20. log
  21. @Initial revision
  22. @
  23. text
  24. @/*
  25.  * bitInt.h --
  26.  *
  27.  *    Definitions used internally by the bit routines, but not
  28.  *    exported to the outside world.
  29.  *
  30.  * Copyright 1988 Regents of the University of California
  31.  * Permission to use, copy, modify, and distribute this
  32.  * software and its documentation for any purpose and without
  33.  * fee is hereby granted, provided that the above copyright
  34.  * notice appear in all copies.  The University of California
  35.  * makes no representations about the suitability of this
  36.  * software for any purpose.  It is provided "as is" without
  37.  * express or implied warranty.
  38.  *
  39.  * $Header: proto.h,v 1.2 88/03/11 08:39:40 ouster Exp $ SPRITE (Berkeley)
  40.  */
  41.  
  42. #ifndef _BITINT
  43. #define _BITINT
  44.  
  45. /*
  46.  * The Bit_FindFirst* routines use a binary search algorithm. Compared with
  47.  * a simple iteration algorithm, the algorithm used below is better because
  48.  * 1) the average execution time is about 10% less.
  49.  * 2) the execution time is relatively independent of the position of 
  50.  *    the bit in the integer. Iteration excution time is proportional to
  51.  *    the bit position.
  52.  *
  53.  * The two Bit_FindFirst* routines use the same basic algorithm. Two macros, 
  54.  * QUICK_TEST and TEST have different definitions depending on the routine.
  55.  *
  56.  * The QUICK_TEST at the top of the loop tests "temp" to see if it needs to be
  57.  * searched. If QUICK_TEST is true, then at least 1 bit is set/cleared in temp.
  58.  * The basic algorithm is "see if that bit is in the right half otherwise it 
  59.  * must be in the left half". 
  60.  */
  61.  
  62. #define SET_QUICK_TEST        if (temp != 0) 
  63. #define CLEAR_QUICK_TEST    if (temp != ~0) 
  64.  
  65. #define SET_TEST(mask)        if ((temp & (mask)) != 0) 
  66. #define CLEAR_TEST(mask)    if ((temp & (mask)) != (mask)) 
  67.  
  68. /*
  69.  * RETURN returns the index of the first bit that is set/cleared in the
  70.  * intNum integer in the array.
  71.  */
  72. #define RETURN(num)     return((intNum*BIT_NUM_BITS_PER_INT)+num);
  73.  
  74. #define FIND_FIRST(numBits, arrayPtr) { \
  75.     register int numInts = Bit_NumInts(numBits); \
  76.     register int temp, intNum; \
  77.     for (intNum = 0; intNum < numInts; intNum++, arrayPtr++) { \
  78.     temp = *arrayPtr; \
  79.     QUICK_TEST { \
  80.         TEST(0x0000ffff) { \
  81.         TEST(0x000000ff) { \
  82.             TEST(0x0000000f) { \
  83.             TEST(0x00000003) { \
  84.                 TEST(0x00000001) { \
  85.                 RETURN(0); \
  86.                 } else { \
  87.                 RETURN(1); \
  88.                 } \
  89.             } else { \
  90.                 TEST(0x00000004) { \
  91.                 RETURN(2); \
  92.                 } else { \
  93.                 RETURN(3); \
  94.                 } \
  95.             } \
  96.             } else { \
  97.             TEST(0x00000030) { \
  98.                 TEST(0x00000010) { \
  99.                 RETURN(4); \
  100.                 } else { \
  101.                 RETURN(5); \
  102.                 } \
  103.             } else { \
  104.                 TEST(0x00000040) { \
  105.                 RETURN(6); \
  106.                 } else { \
  107.                 RETURN(7); \
  108.                 } \
  109.             } \
  110.             } \
  111.         } else { \
  112.             TEST(0x00000f00) { \
  113.             TEST(0x00000300) { \
  114.                 TEST(0x00000100) { \
  115.                 RETURN(8); \
  116.                 } else { \
  117.                 RETURN(9); \
  118.                 } \
  119.             } else { \
  120.                 TEST(0x00000400) { \
  121.                 RETURN(10); \
  122.                 } else { \
  123.                 RETURN(11); \
  124.                 } \
  125.             } \
  126.             } else { \
  127.             TEST(0x00003000) { \
  128.                 TEST(0x00001000) { \
  129.                 RETURN(12); \
  130.                 } else { \
  131.                 RETURN(13); \
  132.                 } \
  133.             } else { \
  134.                 TEST(0x00004000) { \
  135.                 RETURN(14); \
  136.                 } else { \
  137.                 RETURN(15); \
  138.                 } \
  139.             } \
  140.             } \
  141.         } \
  142.         } else { \
  143.         TEST(0x00ff0000) {  \
  144.             TEST(0x000f0000) { \
  145.             TEST(0x00030000) { \
  146.                 TEST(0x00010000) { \
  147.                 RETURN(16); \
  148.                 } else { \
  149.                 RETURN(17); \
  150.                 } \
  151.             } else { \
  152.                 TEST(0x00040000) { \
  153.                 RETURN(18); \
  154.                 } else { \
  155.                 RETURN(19); \
  156.                 } \
  157.             } \
  158.             } else { \
  159.             TEST(0x00300000) { \
  160.                 TEST(0x00100000) { \
  161.                 RETURN(20); \
  162.                 } else { \
  163.                 RETURN(21); \
  164.                 } \
  165.             } else { \
  166.                 TEST(0x00400000) { \
  167.                 RETURN(22); \
  168.                 } else { \
  169.                 RETURN(23); \
  170.                 } \
  171.             } \
  172.             } \
  173.         } else { \
  174.             TEST(0x0f000000) { \
  175.             TEST(0x03000000) { \
  176.                 TEST(0x01000000) { \
  177.                 RETURN(24); \
  178.                 } else { \
  179.                 RETURN(25); \
  180.                 } \
  181.             } else { \
  182.                 TEST(0x04000000) { \
  183.                 RETURN(26); \
  184.                 } else { \
  185.                 RETURN(27); \
  186.                 } \
  187.             } \
  188.             } else { \
  189.             TEST(0x30000000) { \
  190.                 TEST(0x10000000) { \
  191.                 RETURN(28); \
  192.                 } else { \
  193.                 RETURN(29); \
  194.                 } \
  195.             } else { \
  196.                 TEST(0x40000000) { \
  197.                 RETURN(30); \
  198.                 } else { \
  199.                 RETURN(31); \
  200.                 } \
  201.             } \
  202.             } \
  203.         } \
  204.         } \
  205.     } \
  206.     } \
  207.     return(-1); \
  208. }
  209.  
  210. #define GET_MASK_AND_INTS(nB,i,m) \
  211.      i = (nB) / BIT_NUM_BITS_PER_INT; \
  212.     m = ((1 << ((nB) % BIT_NUM_BITS_PER_INT)) - 1)
  213.  
  214. #endif _BITINT
  215. @
  216.